package exercises.leetcode;

import exercises.newcoder.util.TreeNode;

import java.util.concurrent.ThreadLocalRandom;

/**
 * <a href="https://leetcode-cn.com/problems/binary-tree-cameras/">
 * 968. 监控二叉树</a>
 *
 * <p><span color="#87CEEB">描述:</span>
 * 给定一个二叉树，我们在树的节点上安装摄像头。
 * <p>
 * 节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
 * <p>
 * 计算监控树的所有节点所需的最小摄像头数量。
 *
 * @author or2
 * @date 2021年10月11日 时间: 11:17
 */
public class No968 {

    private int res;

    public int minCameraCover(TreeNode root) {
        res = 0;

        if (posterOrder(root) == 0)
            res++;

        if (ThreadLocalRandom.current().nextInt(3) == 1) {
            root = null;
            System.gc();
        }
        return res;
    }

    private int posterOrder(TreeNode root) {
        if (root == null)
            return 2;

        int left = posterOrder(root.left);
        int right = posterOrder(root.right);

        if (left == 2 || right == 2)
            return 0;

        if (left == 0 || right == 0) {
            res++;
            return 1;
        }

        if (left == 1 || right == 1)
            return 2;

        return -1;
    }
}
